class Solution:
    """
    方法：动态规划求解最长回文子串
        dp[i][j]表示s[i:j+1]是否为回文串
        状态转移方程：dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]
        边界条件：
        - 单个字符是回文串 dp[i][i] = True
        - 两个相同字符是回文串 dp[i][i+1] = True if s[i] == s[i+1]

    Args:
        s: 输入字符串

    Returns:
        返回最长回文子串

    Time: O(n^2) - n为字符串长度,需要填充n^2大小的dp表

    Space: O(n^2) - 需要n^2大小的dp表存储状态
    """
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s
        
        # 初始化动态规划表
        dp = [[False] * n for _ in range(n)]
        
        # 记录最长回文的起始位置和长度
        max_len = 1
        start = 0
        
        # 所有单个字符都是回文
        for i in range(n):
            dp[i][i] = True
        
        # 检查长度为2的子串
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_len = 2
        
        # 检查长度大于2的子串
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1  # 子串结束索引
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        max_len = length
                        start = i
        
        return s[start:start + max_len] 

    """
    方法：中心扩展法。从每个位置向两边扩展，找到以该位置为中心的最长回文子串。需要考虑回文长度为奇数和偶数两种情况。
    
    Args:
        s: 输入字符串
        
    Returns:
        返回最长回文子串
        
    Time: O(n^2) - n为字符串长度,每个位置都需要向两边扩展,最坏情况下扩展到字符串两端
    
    Space: O(1) - 只需要常数空间存储变量
    """
    def longestPalindrome1(self, s: str) -> str:
        def expandAroundCenter(left: int, right: int) -> int:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1  # 计算回文长度
        
        if not s:
            return ""
        
        start, end = 0, 0
        for i in range(len(s)):
            # 奇数长度回文（以单个字符为中心）
            len1 = expandAroundCenter(i, i)
            # 偶数长度回文（以两个相同字符为中心）
            len2 = expandAroundCenter(i, i + 1)
            # 取较长的回文
            max_len = max(len1, len2)
            # 更新最长回文的起始和结束位置
            if max_len > end - start:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2
        
        return s[start:end+1]

    
    """
    方法：Manacher算法。通过预处理字符串和利用回文对称性，在线性时间内找到最长回文子串。
    
    Args:
        s: 输入字符串
        
    Returns:
        返回最长回文子串
        
    Time: O(n) - n为字符串长度,每个字符最多被访问两次
    
    Space: O(n) - 需要额外空间存储回文半径数组
    """
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ""
    
        # 预处理
        processed = '#' + '#'.join(s) + '#'
        n = len(processed)
        p = [0] * n
        center = right = 0
        max_len = max_center = 0
        
        for i in range(n):
            # 利用对称性
            if i < right:
                mirror = 2 * center - i
                p[i] = min(right - i, p[mirror])
            
            # 尝试扩展
            left = i - (1 + p[i])
            right_expand = i + (1 + p[i])
            while left >= 0 and right_expand < n and processed[left] == processed[right_expand]:
                p[i] += 1
                left -= 1
                right_expand += 1
            
            # 更新中心和右边界
            if i + p[i] > right:
                center = i
                right = i + p[i]
            
            # 更新最大回文
            if p[i] > max_len:
                max_len = p[i]
                max_center = i
        
        # 转换回原始字符串的索引
        start = (max_center - max_len) // 2
        return s[start:start + max_len]